package everyday.apr;

/**
 * 744. 寻找比目标字母大的最小字母
 */
public class Day3 {
    public static void main(String[] args) {
        System.out.println(nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'a'));
        System.out.println(nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'c'));
        System.out.println(nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'j'));
    }

    /**
     * 线性查找
     */
    public static char nextGreatestLetter(char[] letters, char target) {
        int min = 100;
        for (char letter : letters) {
            int temp = letter - target > 0 ? letter - target : letter - target + 26;
            min = Math.min(min, temp);
        }
        return (char) ('a' + (target - 'a' + min) % 26);
    }

    /**
     * 二分查找
     */
    public char nextGreatestLetter1(char[] letters, char target) {
        int length = letters.length;
        if (target >= letters[length - 1]) {
            return letters[0];
        }
        int low = 0, high = length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return letters[low];
    }
}
